import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
       }
}

class Solution {
        //解法1:递归解法
    public List<Integer> inorderTraversal(TreeNode root) {
        //创建一个数组列表存储节点val值
        List<Integer> list = new ArrayList();
        //树为空,返回空列表
        if(root == null) return list;
        //左
        list.addAll(inorderTraversal(root.left));
        //根
        list.add(root.val);
        //右
        list.addAll(inorderTraversal(root.right));
        return list;
    }
        //解法2:迭代解法
        public List<Integer> inorderTraversal2(TreeNode root) {
            //创建数组列表存储节点val值
            List<Integer> list = new ArrayList();
            //树为空返回空列表
            if(root == null) return list;
            //创建辅助栈
            Stack<TreeNode> stack = new Stack();
            //node标记当前节点
            TreeNode node = root;
            //若栈非空或当前节点非空,遍历树
            while (!stack.isEmpty() || node != null) {
                //找到最左下侧的节点,并依次入栈
                while (node != null) {
                    stack.push(node);
                    node = node.left;
                }
                //此时node为null,已找到最左下侧节点,node保存该节点,辅助栈弹出栈顶元素(即左下侧节点)
                node = stack.pop();
                //将当前节点val值添加到数组列表
                list.add(node.val);
                //节点右移,继续遍历
                node = node.right;
            }
            return list;
        }
    }
}